Lucas 定理

设 $p$ 素数, $m$ 和 $n$ 是非负整数. 则

\[
\binom{m}{n}\equiv\prod_{i=0}^{k}\binom{m_i}{n_i}\pmod p
\]

其中

\[
\begin{aligned}
m&=m_k p^k+m_{k-1}p^{k-1}+\cdots+m_1 p+m_0,\\
n&=n_k p^k+n_{k-1}p^{k-1}+\cdots+n_1 p+n_0,\\
\end{aligned}
\]

约定 $\binom{m}{n}=0$, 如果 $m < n$.

一个直接推论是 $p|\binom{m}{n}$ 当且仅当存在 i, 使得 $n_i > m_i$.

例子: 设 $p$ 是素数, $m\geqslant 1$, $0\leqslant k\leqslant p-1$, 证明

\[
\binom{mp+k}{p}\equiv m\pmod p
\]

References:

https://en.wikipedia.org/wiki/Lucas%27_theorem